\documentclass[12pt]{article}
\usepackage{times}
\usepackage{graphicx}
\usepackage{sidecap}
\usepackage{wrapfig}
\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\baselinestretch}{1.2}
\newenvironment{mylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}
\newenvironment{mylisting2}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}

%%% This file is Open Content

\begin{document}
	\textbf{{\Huge Collision detection with raycasting - recursive dimensional clustering}}
{\center{17 Apr, 2012, 
	Johan Ceuppens, Theo D'Hondt - Vrije Universiteit Brussel}}
\\
{\large{\textbf{\center Abstract}}}
\\

Tesselation between projected lines can yield results for collision detection.
This paper shows how you can achieve this.\\


\section{\large Introduction}

By intersecting lines in clusters you can calculate sniping in games of a 
3D world. Clusters intersect with lines coming out of corners of the frustum.
These lines can be cached to propagate intensive collision detection.

Propagation of lines between 2 lines yield a fast tesselating mechanism to
cause the 2 lines or the lines in between (the tesselated lines) 
to collide somewhere. This functionality can be added to GPU code 
(in-core or with a software system.)
\begin{figure}[h!]
\caption{Single Tesselation between cached collision lines (line 1 and line 2)}
\includegraphics{frustum3.eps} 
\end{figure}

Scheme code follows.


\begin{mylisting}
\begin{verbatim}

	
;;Copyright (c) 2012, Johan Ceuppens 
;;All rights reserved.

;;Redistribution and use in source and binary forms, with or without
;;modification, are permitted provided that the following conditions are met:
;;1. Redistributions of source code must retain the above copyright
;;   notice, this list of conditions and the following disclaimer.
;;2. Redistributions in binary form must reproduce the above copyright
;;   notice, this list of conditions and the following disclaimer in the
;;   documentation and/or other materials provided with the distribution.
;;3. All advertising materials mentioning features or use of this software
;;   must display the following acknowledgement:
;;   This product includes software developed by the <organization>.
;;4. Neither the name of the <organization> nor the
;;   names of its contributors may be used to endorse or promote products
;;   derived from this software without specific prior written permission.

;;THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ''AS IS'' AND ANY
;;EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
;;WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
;;DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
;;DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
;;(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
;;	    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
;;	    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
;;	    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
;;	    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


;; This is the naive solution of recursive removal for collision detection in 3D worlds

(define threshold 1.3)

(define (sqr X)
  (* X X))

(define (distance x1 y1 z1 x2 y2 z2)
	(sqrt
	  (+ (sqr (- x2 x1))
     	     (sqr (- y2 y1))
             (sqr (- z2 z1)))))

(define (make-ray-db)
  (let ((*db '())
	(*threshold threshold))

	;; private functions

	(define (make-point x1 y1 z1)
	  (list x1 y1 z1))

	(define (make-point-first p)
	  (car p))

	(define (make-point-second p)
	  (cadr p)))

	(define (point-x p)
	  (car p))

	(define (point-y p)
	  (cadr p))

	(define (point-z p)
	  (caddr p))


	(define (make-ray1 x1 y1 z1 x2 y2 z2)
	  (append (list (make-point x1 y1 z1))
		  (list (make-point x2 y2 z2))))

	(define (db-add x1 y1 z1 x2 y2 z2)
	 (append *db (list (make-ray1 x1 y1 z1 x2 y2 z2))))

	(define (db-add-t x1 y1 z1 t1 x2 y2 z2 t2)
	  #f)

	;; public functions
	(define (make-ray x1 y1 z1 x2 y2 z2)
		(db-add x1 y1 z1 x2 y2 z2))

	(define (collision? x y z)
		(do ((i 0 (+ i 1))
		     (li (car *db) (cdr li)))
		  ((cond ((null? li) #f)
			 ((let ((p1 (make-point-first li))
				(p2 (make-point-second li)))
			    (or (< (distance x y z (point-x p1)(point-y p1)(point-z p1)) *threshold)
			        (< (distance x y z (point-x p2)(point-y p2)(point-z p2)) *threshold))
			  li))
			 (else #f) 
		  ))
		  ))

	(lambda (msg)
	  (cond ((eq? 'make-ray) make-ray)
		((eq? 'collision?) collision?)
		(else (display "ray-db : message not understood")(display msg)(newline)))))

;; end of code 

;;Copyright (c) 2012, Johan Ceuppens 
;;All rights reserved.

;;Redistribution and use in source and binary forms, with or without
;;modification, are permitted provided that the following conditions are met:
;;1. Redistributions of source code must retain the above copyright
;;   notice, this list of conditions and the following disclaimer.
;;2. Redistributions in binary form must reproduce the above copyright
;;   notice, this list of conditions and the following disclaimer in the
;;   documentation and/or other materials provided with the distribution.
;;3. All advertising materials mentioning features or use of this software
;;   must display the following acknowledgement:
;;   This product includes software developed by the <organization>.
;;4. Neither the name of the <organization> nor the
;;   names of its contributors may be used to endorse or promote products
;;   derived from this software without specific prior written permission.

;;THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ''AS IS'' AND ANY
;;EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
;;WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
;;DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
;;DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
;;(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
;;	    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
;;	    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
;;	    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
;;	    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
)

;; This is the less naive solution of recursive removal for collision detection in 3D worlds
;; The fraction is a get together of 2 cornered lines into 3D space / into the frustum
;;


(define threshold 1.3)

(define (sqr X)
  (* X X))

(define (distance-frustum x1 y1 z1 x2 y2 z2)
	(* fraction
	   (sqrt
	    (+ (sqr (- x2 x1))
     	     (sqr (- y2 y1))
             (sqr (- z2 z1))))))


(define (make-ray-db)
  (let ((*db '())
	(*threshold threshold)
	(*theta1 0.2)
	(*theta2 0.2)
	(*theta3 0.2)

     (let ((*frustum-scale 
	     (lambda (x y z theta1 theta2 theta3)
			(make-point (* x theta1)
		    		    (* y theta2)
		                    (* z theta3)))))

	;; private functions

	(define (make-point x1 y1 z1)
	  (list x1 y1 z1))

	(define (make-point-first p)
	  (car p))

	(define (make-point-second p)
	  (cadr p)))

	(define (point-x p)
	  (car p))

	(define (point-y p)
	  (cadr p))

	(define (point-z p)
	  (caddr p))


	(define (make-ray1 x1 y1 z1 x2 y2 z2)
	  (append (list (make-point x1 y1 z1))
		  (list (make-point x2 y2 z2))))

	(define (db-add x1 y1 z1 x2 y2 z2)
	 (append *db (list (make-ray1 x1 y1 z1 x2 y2 z2))))

	(define (db-add-t x1 y1 z1 t1 x2 y2 z2 t2)
	  #f)


	;; public functions
	(define (make-ray x1 y1 z1 x2 y2 z2)
		(db-add x1 y1 z1 x2 y2 z2))

	(define (collision? x y z)
		(do ((i 0 (+ i 1))
		     (li (car *db) (cdr li)))
		  ((cond ((null? li) #f)
			 ((let ((p1 (make-point-first li))
				 (p2 (make-point-second li)))
			    (let ((p1 (*frustum-scale (point-x p1)
						     (point-y p1)
						     (point-z p1)
						     *theta1 *theta2 *theta3))
				 (p2 (*frustum-scale (point-x p2)
						    (point-y p2)
						    (point-z p2)
						    *theta1 *theta2 *theta3)))

			    (< (distance-frustum 
				     (point-x p1)(point-y p1)(point-z p1)
			       	     (point-x p2)(point-y p2)(point-z p2))
				   *threshold)
			  li)))
			 (else #f) 
		  )
		  (set! *theta1 (* *theta1 0.9))
		  (set! *theta2 (* *theta2 0.9))
		  (set! *theta3 (* *theta3 0.9))
		  )))

	(lambda (msg)
	  (cond ((eq? 'make-ray) make-ray)
		((eq? 'collision?) collision?)
		(else (display "ray-db : message not understood")(display msg)(newline))))))


;; end of code 

\end{verbatim}
\end{mylisting}


\section{\large Conclusion}

Dimensional clusters can be added to the cache system of rays to replete
collision detection. Dimensional clusters are areas in 3D space where the
tesselated lines in between raycasting lines can cross the cluster. By
allowing GPU to calculate this using their own tesselation (e.g. with quaternions) one can provide a simple discrete collision detection system.

\bibliographystyle{plain}
\bibliography{refs} % refs.bib

\end{document}


